package com.wei.ds;

import java.awt.*;
import java.nio.charset.CharsetEncoder;

/**
 * 八皇后问题（英文：Eight queens），是由国际西洋棋棋手马克斯·贝瑟尔于1848年提出的问题，是回溯算法的典型案例。
 * 问题表述为：在8×8格的国际象棋上摆放8个皇后，使其不能互相攻击，
 * 即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。
 * 高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，
 * 后来有人用图论的方法解出92种结果。
 * 如果经过±90度、±180度旋转，和对角线对称变换的摆法看成一类，共有42类。
 * 计算机发明后，有多种计算机语言可以编程解决此问题。
 *
 * @Author :sunwei
 * @Description:
 * @Date create in 22:27  2020/7/9
 * @Modified by:
 */
public class EightQueen {
    private int max = 8;
    /*
     * array 表示棋盘,array的下标表示行,array的值表示列
     */
    private int[] array = new int[max];
    private int resultNum;

    public void run() {
        resultNum = 0;
        runInner(0);
        System.out.println("the Number of resolver is " + resultNum);
    }

    /**
     * <p>走棋实现,先从第一行放,之后依次放其他行,每次放都检查,合规就放下一行.</p>
     *
     * @param num (下标)表示是第几个皇后
     * @return void
     * @version 0.1.0
     * @author SunWei
     * @date 2020/7/9 22:41
     * @since 0.1.0
     */
    private void runInner(int num) {
        if (num == max) { //如果已经走到下标为8说明是第9个皇后了,表示找到一种解法.
            printResult();
            resultNum++;
            return;
        }
        for (int i = 0; i < max; i++) {
            array[num] = i; //从0到max分别放置皇后
            if (check(num)) {//检查皇后是否合规
                runInner(num + 1);//合规则放下一个皇后
            }
            //如果不合规,则再移动列 即i++
        }
    }

    private void printResult() {
        for (int i = 0; i < array.length; i++) {
            int colIndex = array[i];
            for (int j = 0; j < max; j++) {
                if (colIndex == j) {
                    System.out.print("1" + " ");
                } else {
                    System.out.print("0" + " ");
                }
            }
            System.out.println();
        }
        System.out.println("==============");
    }

    /**
     * <p>判断当前皇后的位置是否合规,斜率为1则表示有皇后在斜线上</p>
     *
     * @param num 表示第几个皇后
     * @return boolean
     * @version 0.1.0
     * @author SunWei
     * @date 2020/7/9 22:44
     * @since 0.1.0
     */
    private boolean check(int num) {
        for (int row = 0; row < num; row++) {
            /*
             * array[row] == array[num]
             * 表示有皇后在同一列
             *
             * Math.abs(num - row) == Math.abs(array[num] - array[row])
             * Math.abs(num - row):行距
             * Math.abs(array[num] - array[row]):列距
             * 行距=列距表示有皇后在斜线上，斜率为1
             */
            if (array[row] == array[num] || Math.abs(num - row) == Math.abs(array[num] - array[row])) {
                return false;
            }
        }
        return true;
    }

}
